﻿//410. 分割数组的最大值
//给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组，使得这 k 个子数组各自和的最大值 最小。
//返回分割后最小的和的最大值。
//子数组 是数组中连续的部份。



class Solution {
public:
    int splitArray(vector<int>& nums, int k)
    {
        auto check = [&](int m)->bool
        {
            int cnt = 1, sum = 0;
            for (auto& x : nums)
            {
                if (sum + x <= m)
                {
                    sum += x;
                }
                else
                {
                    cnt++;
                    if (cnt == k + 1)
                    {
                        return false;
                    }
                    sum = x;
                }
            }
            return true;
        };
        int left = ranges::max(nums), right = accumulate(nums.begin(), nums.end(), 0);
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(mid))
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};